#include <iostream>

using namespace std;

//merge sorted elems of inp[] in range [left, mid) with sorted elems in range [mid, right);
void merge(int inp[], int left, int mid, int right, int buffer[]) {
	int l = left;
	int r = mid;
	int i = left;
	/*
	while (l < mid || r < right) {
		if(l < mid && r < right) {
			if(inp[l] < inp[r]) {
				buffer[i] = inp[l];
				++l;
			} else {
				buffer[i] = inp[r];
				++r;
			}
		} else if(l < mid) {
			buffer[i] = inp[l];
			++l;
		} else {
			buffer[i] = inp[r];
			++r;
		}
		++i;
	}
	*/
	while (l < mid && r < right) {
		if(inp[l] < inp[r]) {
			buffer[i] = inp[l];
			++l;
		}
		else {
			buffer[i] = inp[r];
			++r;
		}
		++i;
	}
	while(l < mid) {
		buffer[i] = inp[l];
		++i;
		++l;
	}
	while(r < right) {
		buffer[i] = inp[r];
		++i;
		++r;
	}

	//copy back from buffer helper to inp
	for(i = left; i < right; ++i)
		inp[i] = buffer[i];
}

//buffer capacity is <= size
void mergeSort_internal(int inp[], int size, int buffer[]) {

	if(size <= 1) return;
	int mid = size / 2;

	mergeSort_internal(inp, mid, buffer);
	mergeSort_internal(inp + mid, size - mid, buffer);
	merge(inp, 0, mid, size, buffer);
}

void mergeSort(int inp[], int size) {
	int *buffer = new int[size];
	mergeSort_internal(inp, size, buffer);
	delete[] buffer;
}

int main()
{
	int size;
	cout << "enter array size:\n";
	cin >> size;
	int *array = new int[size];
	for(int i = 0; i < size; ++i) {
		cout << "enter element [" << i <<"] :\n";
		cin >> array[i];
	}
	cout << "Sorted array is :\n";
	mergeSort(array, size);
	int i = 0;
	for(i = 0; i < size-1; ++i) {
		cout << array[i] << ", ";
	}
	cout << array[i] << endl;
	delete[] array;
	return 0;
}
